package javatest.algorith;

import java.util.HashMap;
import java.util.HashSet;

/*
 * 无向图
 */
public class Graph {
    public HashMap<String, Node> nodes = new HashMap<>();
    public HashMap<String, Integer> distanceMap = new HashMap<>();       // 记录原数据
    public HashMap<String, Integer> minDistanceMap = new HashMap<>();    // 记录最短路径

    public static void main(String[] args) {
        String[] items = {"1 2 4", "2 3 10", "3 4 100", "4 5 30", "3 5 20", "1 4 13"};
        Graph g = new Graph();
        String sourceName;
        String targeName;
        int distance;
        System.out.println("===== source =====");
        for (String item : items) {
            sourceName = item.split(" ")[0];
            targeName = item.split(" ")[1];
            distance = Integer.parseInt(item.split(" ")[2]);
            System.out.println(String.format("%s -> %s: %s", sourceName, targeName, distance));
            g.addNode(sourceName, targeName, distance);
        }
        
        sourceName = "1";
        g.dijkstra(sourceName); // 计算 1 到其他节点的最短距离
        System.out.println("===== result: min distance of '1' =====");
        for (String targetName : g.nodes.keySet()) {
            distance = g.getDistance("1", targetName);
            System.out.println(String.format("%s -> %s : %s", sourceName, targetName, distance));
        }
        
    }
    /*
     * 狄杰斯特拉算法求最短路径, 距离都是大于0的
     */
    public void dijkstra(String sourceName){

        Node source = nodes.get(sourceName);

        nodes.forEach((name, cur) -> {
            cur.nexts.forEach((next)->{
                int sourceToCurrent = getDistance(source, cur);
                int currentToNext = getDistance(cur, next);
                int sourceToNext = getDistance(source, next);
                int newDistance = sourceToCurrent + currentToNext;

                if(sourceToNext > newDistance){
                    String key = creatKey(source.name, next.name);
                    minDistanceMap.put(key, newDistance);
                }
            });

        });
        // return getDistance(source, target);
    }

    public void addNode(String sourceName, String targeName, int distance){
        if (!nodes.containsKey(sourceName)) nodes.put(sourceName, new Node(sourceName));
        if (!nodes.containsKey(targeName)) nodes.put(targeName, new Node(targeName));
        Node source = nodes.get(sourceName);
        Node target = nodes.get(targeName);
        source.addNext(target);
        target.addNext(source);

        String key = creatKey(sourceName, targeName);
        
        distanceMap.put(key, distance);
        minDistanceMap.put(key, distance);
    }
    
    private int getDistance(Node source, Node target){
        String key = creatKey(source.name, target.name);
        if (source == target) minDistanceMap.put(key, 0);
        if (!minDistanceMap.containsKey(key)) minDistanceMap.put(key, Integer.MAX_VALUE);
        return minDistanceMap.get(key);
    }

    private int getDistance(String sourceName, String targetName){
        return getDistance(nodes.get(sourceName), nodes.get(targetName));
    }

    private String creatKey(String sourceName, String targeName){
        return sourceName.compareTo(targeName) < 0 ?
        sourceName+ " -> " +targeName : targeName + " -> " +sourceName;
    }

    public class Node{
        public String name;
        public HashSet<Node> nexts = new HashSet<>();
        
        Node(String name) {
            this.name = name;
        }

        public void addNext(Node target){
            nexts.add(target);
        }
    }
}
